package leetcode.editor.cn;

//Java：有序数组的平方
public class SquaresOfASortedArray {
    public static void main(String[] args) {
        Solution solution = new SquaresOfASortedArray().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        /**
         * 思路：该题特点：数组有序
         * 那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
         * 此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
         * 定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
         * 如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j];
         * 如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i];
         *
         * @param nums 待排序的数组
         * @return int[] 排好序的数组
         */
        public int[] sortedSquares(int[] nums) {
            int left = 0;
            int right = nums.length - 1;
            int[] result = new int[nums.length];
            int index = result.length - 1;
            while (left <= right) {
                if (nums[left] * nums[left] > nums[right] * nums[right]) {
                    result[index--] = nums[left] * nums[left];
                    left++;
                } else {
                    result[index--] = nums[right] * nums[right];
                    right--;
                }
            }
            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}